package com.my.code.algorithm;

import java.util.PriorityQueue;

/**
 * <b>求数组中位数</b><p>
 * 偶数数组，返回中间两个元素的第一个
 * 使用最小堆的方式 PriorityQueue默认的数据结构就是小顶堆
 *
 * @author zzl
 * @date 2020/10/29
 */
public class TestMid2 {

    public static void main(String[] args) {
        int[] arr = {4, 6, 7, 0, 2};
        int median = median(arr);
        System.out.println("median = " + median);
    }

    @SuppressWarnings("all")
    private static int median(int[] arr) {
        int heapSize = arr.length / 2 + 1;
        PriorityQueue<Integer> heap = new PriorityQueue<>(heapSize);
        for (int i = 0; i < heapSize; i++) {//取数组前一半放入堆中（小顶堆）
            heap.add(arr[i]);
        }
        for (int i = heapSize; i < arr.length; i++) {//将数组的后一半与堆中比较，置换出堆中较小的值
            if (heap.peek() < arr[i]) {
                heap.poll();
                heap.add(arr[i]);
            }
        }
        return heap.peek();
    }
}
